package com.gxc.graph;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 被围绕的区域
 * 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' 组成，捕获 所有 被围绕的区域：
 *
 * 连接：一个单元格与水平或垂直方向上相邻的单元格连接。
 * 区域：连接所有 'O' 的单元格来形成一个区域。
 * 围绕：如果您可以用 'X' 单元格 连接这个区域，并且区域中没有任何单元格位于 board 边缘，则该区域被 'X' 单元格围绕。
 * 通过 原地 将输入矩阵中的所有 'O' 替换为 'X' 来 捕获被围绕的区域。你不需要返回任何值。
 */
public class Solve {

    public static void main(String[] args) {
        solve(new char[][]{{'X','X','X','X'},
                {'X','O','O','X'},
                {'X','X','O','X'},
                {'X','O','X','X'}});
        System.out.println("---");
    }

    public static void solve(char[][] board) {
        Queue<int[]> queue = new LinkedList<>();
        int m = board.length, n = board[0].length;
        for (int i = 0; i < n; i++) {
            if (board[0][i] == 'O') {
                queue.add(new int[]{0, i});
                board[0][i] = 'A';
            }
            if (board[m-1][i] == 'O') {
                queue.add(new int[]{m-1, i});
                board[m-1][i] = 'A';
            }
        }
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                queue.add(new int[]{i, 0});
                board[i][0] = 'A';
            }
            if (board[i][n-1] == 'O') {
                queue.add(new int[]{i, n-1});
                board[i][n-1] = 'A';
            }
        }

        int[][] dirs = new int[][]{{0,1}, {1,0}, {0,-1}, {-1,0}};

        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            for (int i = 0; i < dirs.length; i++) {
                int x = poll[0] + dirs[i][0];
                int y = poll[1] + dirs[i][1];
                if (x>=0 && x<m && y>=0 && y<n && board[x][y] == 'O') {
                    queue.add(new int[]{x, y});
                    board[x][y] = 'A';
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == 'A'){
                    board[i][j] = 'O';
                }
            }
        }
    }

}
